1. Field of the Invention
The present invention relates to an encryption system, and more particularly to data security, acknowledgement of sender and receiver, sharing of cryptographic key and zero knowledge certification protocol in a field of cryptocommunication.
2. Related Background Art
Prior art encryption system may be classified into two major categories. In one category of encryption system, a cryptographic key may be cryptoanalyzed if a certain number of cryptograms are available, that is, all of subsequently outputted cryptograms can be readily cryptoanalyzed. Such an encryption system is referred to as a system A. Typical examples of the system A are the Feistel encryption such as DES (Data Encryption Standard) or FEAL (Fast Encryption Algorithm), or linear feedback shift register system (hereinafter LFSR system) or non-linear feedback shift register system which uses a shift register.
As shown in FIG. 12, the LFSR system comprises a stages of shift registers R(t)=(r.sub.s (t), r.sub.s-1 (t), . . . , r.sub.2 (t), r.sub.1 (t)) and tap train (h.sub.s, h.sub.s-1, . . . , h.sub.2, h.sub.1). It simultaneously performs the following operations for each time point (stop) to generate a pseudo-random number sequence.
(a) Output the bit r.sub.1 (t) of the rightmost register as a pseudo-random sequence EQU k.sub.t =r.sub.1 (t) PA0 (b) Shift right r.sub.s (t), r.sub.s-1 (t), . . . , r.sub.2 (t) EQU r.sub.i (t+1)=r.sub.i+1 (t) PA0 (i=1, 2, . . . , s-1) PA0 (c) Calculate the bit r.sub.s (t+1) of the leftmost register based on the content of the register and the tap train. ##EQU1##
To summarize the above, the pseudo-random number sequence generation algorithm of the LFSR system can be expressed by using an s-row and s-column matrix H as follows: EQU R(t+1)=H.multidot.R(t) mod2 (1)
Namely, ##EQU2##
By properly selecting the tap train of the s-stage LFSR, a pseudo-random bit sequence having a maximum period of 2.sup.s -1 may be generated and the sequence thereof is the maximum period sequence described above.
However, in the random number sequence generation method using the LFSR, the s-stage tap train (h.sub.s, h.sub.s-1, . . . , h.sub.2, h.sub.1) may be determined based on 2s-bit output pseudo-random number sequence in the following manner by utilizing the linearity of the LFSR.
Assuming that the output pseudo-random number sequence is k.sub.1, k.sub.2, . . . , k.sub.2s, the contents R(t) of the reigster at time points t (t=1, 2, . . . , s+1) are represented by: ##EQU3## where .sup.T represents transposition. When matrices X and Y are given by: EQU X=(R(1), R(2), . . . , R(s)) EQU Y=(R(2), R(3), . . . , R(s+1))
the following relation is met from the formula (1); EQU Y=H.multidot.X,
that is; EQU H=Y.multidot.X.sup.-1 ( 2)
Thus, H is determined and the tap train is determined.
Namely, the period of the random number sequence is 2.sup.s -1 and the construction of the LFSR is determined by 2s bits. In this case, since all random number sequences generated after that time point are known, the use of the output random number sequence for the encryption purpose is not appropriate in terms of security.
It is known that the number of random numbers which require the analysis of the output random number sequences increases when the non-linear feedback shift register is used. However, the LFSR of a minimum number of stages which can generate the sequence may be determined by Berlekamp-Massey algorithm (E. R. Berlekamp "Algebraic Coding Thoery", McGraw-Hills Books Company, 1968), and the random number sequence generation system using the non-linear feedback shift register may be analyzed by the method of the formula (2).
In the DES and the FEAL, a search faster than an overall key search (search for 2.sup.56 keys) may be attained by a cryptoanalysis method called a differential cryptoanalysis (E. Biham, A. Shamir: "Differential Cryptoanalysis of DES-like Cryptosystems", Journal of Cryptology, Vol. 4, No. 1, pp. 3-72, 1992). In a recent study, it is shown that the 16-stages of DES can be cryptoanalyzed by 2.sup.47 known ordinary text attack, the 8-stage DES can be cryptoanalyzed by 2.sup.21 known ordinary text attack, and the 8-stage FEAL can be cryptoanalyzed by 2.sup.15 known ordinary text attack, and it is expected that the number of searches will decrease as the study progresses.
However, those systems are frequently used in practice because high speed encryption operation may be attained by a simple operation. Thus, the system A attains the high speed operation although it does not assure the security.
On the other hand, unlike the system A, an encryption system in which it is very difficult to predict an encrypted output which will be subsequently generated from only the encrypted output generated before a certain time point is referred to as a system B. Where the encrypted output is a random number, a typical example of the system B is a square residue operation method disclosed in an article "Advances in Cryptology" (PLENUM PRESS, pp. 61-78, 1983). In this method, when the random number sequence is represented by {b.sub.1, b.sub.2, . . . , }, the bit b.sub.i is given by; EQU x.sub.i+1 =x.sub.i.sup.2 mod n
(i=0, 1, 2, . . . ) EQU b.sub.i =1sb(x.sub.i)
(i=0, 1, 2, . . . )
where x.sub.0 is an arbitrarily given initial value, n=p.multidot.q (p, q are principle numbers) and 1sb(x) represents a least significant bit of x.
It is known that the determination of b.sub.i+1 from only the random number sequence {b.sub.1, b.sub.2, . . . , b.sub.i } generated by this method is as much time-taking as that for factorizing n. Namely, the amount of calculation for determining the random numbers generated after a time point based on the random numbers generated by that time point is equivalent to the amount of calculation required for factorizing n. The random number given by this method is hereinafter referred to as a square residue random number. (b.sub.1 may not comprise only the least significant bit of x.sub.i bit it may comprise the least significant bit to the log.sub.2 n bit.)
However, in order to make it difficult in terms of the amount of calculation to factorize n, it is necessary to increase p and q to several hundreds of bits. The random numbers generated by the method which makes it difficult in terms of the amount of calculation to predict the random numbers which will be generated subsequently based on the random number sequence generated by that time point is referred to as cryptologically secure pseudo-random numbers.
In the above case, the amount of calculation for calculating x.sub.i+1 =x.sub.i.sup.2 mod n is also large and the random number cannot be generated at a high speed. Namely, as opposed to the system A, the system B assures the security but cannot attain the high speed operation. Another example of the system B is a discrete logarithmic random number (M. Blum and S. Micali: "How to generate cryptographically strong sequences of pseudo-random bits", 23rd IEEE FOCS, pp. 112-117, 1982) which assures the same security as that of determining an RSA random number (B. Chor and O. Goldreich: "RSA/Rabin least significant bits are 1/2+1/poly(n) secure", Advances in Cryptology: Proceedings of Crypto 84, G. R., 1984) or discrete logarithm. It still has a similar feature that it assures the security but does not attain the high speed operation. Thus, the system A allows the high speed operation but does not assure the security while the system B, unlike the system A, assures the security in terms of the amount of calculation but does not attain the high speed operation.